package org.czx.datactruct.eight;

import java.util.Arrays;

/**
 * @author czx
 * @date 2020/9/22 16:14
 */
public class SortArray {

    public static void main(String[] args) {
        Integer[] array = {16, 13, 2, 10, 11, 3, 6, 7, 8, 0, 5, 4, 15, 1, 14, 12, 9, 17, 18, 19};
        shellSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * Sorts the entries of an array a[first...last] into ascending order.
     *
     * @param a     An array of Comparable objects.
     * @param first An integer containing the beginning index. 0 <= first < a.length
     * @param last  An integer containing the last index. first <= last < a.length
     */
    public static <T extends Comparable<? super T>> void shellSort(T[] a, int first, int last) {
        // The difference betweeen the indices of the entries to sort.
        for (int space = a.length / 2; space > 0; space = space / 2) {
            for (int begin = first; begin < first + space; begin++) {
                incrementalInsertionSort(a, begin, last, space);
            }
        }
    }

    // Sorts equally spaced entries of an array a[first...last] into ascending order
    //  0 <= first < a.length , first <= last < a.length
    private static <T extends Comparable<? super T>> void incrementalInsertionSort(T[] a, int first, int last, int space) {
        T nextToInsert;
        int index;
        for (int unsorted = first + space; unsorted <= last; unsorted += space) {
            nextToInsert = a[unsorted];
            index = unsorted - space;
            while (index >= first && nextToInsert.compareTo(a[index]) < 0) {
                a[index + space] = a[index];
                index = index - space;
            }
            a[index + space] = nextToInsert;
        }
    }


    public static <T extends Comparable<? super T>> void insertionSortRecursive(T[] a, int first, int last) {
        if (first < last) {
            insertionSortRecursive(a, first, last - 1);
            insertInOrder(a[last], a, first, last - 1);
        }
    }

    /**
     * 插入排序
     *
     * @param a
     * @param first
     * @param last
     * @param <T>
     */
    public static <T extends Comparable<? super T>> void insertionSort(T[] a, int first, int last) {
        for (int unSorted = first + 1; unSorted < last; unSorted++) {
            T nextToInsert = a[unSorted];
            insertInOrder(nextToInsert, a, first, unSorted - 1);
        }
    }

    /**
     * 插入排序
     *
     * @param a An array of Comparable objects.
     * @param n An integer > 0
     */
    public static <T extends Comparable<? super T>> void selectionSort(T[] a, int n) {
        for (int index = 0; index < n - 1; index++) {
            int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
            swap(a, index, indexOfNextSmallest);
        }
    }

    /**
     * 插入排序的递归代码
     *
     * @param a
     * @param first
     * @param last
     * @param <T>
     */
    public static <T extends Comparable<? super T>> void selectionSortRecursive(T[] a, int first, int last) {
        if (first < last) {
            int indexOfNextSmallest = getIndexOfSmallest(a, first, last);
            swap(a, first, indexOfNextSmallest);
            selectionSortRecursive(a, first + 1, last);
        }
    }

    /**
     * 从数组的begin到end之间,找到合适的位置，插入anEntry元素
     *
     * @param anEntry
     * @param a
     * @param begin
     * @param end
     * @param <T>
     */
    private static <T extends Comparable<? super T>> void insertInOrder(T anEntry, T[] a, int begin, int end) {
        int index = end;
        for (; index >= begin && anEntry.compareTo(a[index]) < 0; index--) {
            a[index + 1] = a[index];  //腾出空间
        }
        a[index + 1] = anEntry;
    }


    // Finds the index of the smallest value in a portion of an array a.
    // Precondition: a.length > last >= first >= 0.
    // Returns the index of the smallest value among
    // a[first], a[first + 1], . . . , a[last].
    private static <T extends Comparable<? super T>> int getIndexOfSmallest(T[] a, int first, int last) {
        T min = a[first];
        int indexOfMin = first;
        for (int index = first; index <= last; index++) {
            if (a[index].compareTo(min) < 0) {
                min = a[index];
                indexOfMin = index;
            }
        }
        return indexOfMin;
    }

    // Swaps the array entries a[i] and a[j].
    private static void swap(Object[] a, int i, int j) {
        Object temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
